package cn.sirann;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @author: siran.yao
 * @date: 2020/6/17 22:35
 */
public class MinDistance {

    /**
     * 思路：houses = [1,4,8,10,20], k = 3
     * 题目原意：在houses 数组中，插入3个信箱，使得信箱与周边房子的差值最小。
     * 可以理解为：把一段距离，分隔成 k 段， 每段 k 的最小值加起来就是结果。 类似forkjoin 思想
     * <p>
     * 转移方程：f[i][j][k] = min(f[i][j],f[i-1][k-1] + distance[i][j]);
     *
     * dp 表中：
     * k 表示邮筒
     * i,j 表示 房子的起始和结尾
     * 1.f[i-1][k-1] 表示上一个距离 有 k个邮筒的最短距离
     * 2.distance[i][j] 表示i房子 与 j房子之间最短的距离
     *
     *
     *      0     1           4           8             10            20
     * 0    /     /           /          /              /             /
     * 1    /  dis[1][1]  dis[2][1]   dis[3][1]      dis[4][1]      dis[5][1]  这里表示从哪个房子往前的范围中放置1个邮筒 最短距离。
     * 2    /                                                           接下来的2个邮筒 或者三个邮筒 就是根据相同范围进行比较
     * 3    /                                                           转移方程： f[i][j][k] = min(f[i][j],f[i-1][k-1] + distance[i][j]);
     */
    public int minDistance(int[] houses, int k) {
        // bound check
        int len = houses.length;
        if (len == 0)
            return 0;

        // sort
        Arrays.sort(houses);

        // compute i - j minimum value by one postbox
        int[][] distance = new int[len + 1][len + 1];
        for (int i = 1; i <= len; i++) {
            for (int j = i; j <= len; j++) {
                int mid = i + j >> 1;
                int t = 0;
                for (int u = i; u <= j ; u++) {
                    t += Math.abs(houses[u - 1] - houses[mid - 1]);
                }
                distance[i][j] = t;
            }
        }

        // fill default value
        int[][] dp = new int[len + 1][k + 1];
        for (int i = 0; i <= len; i++) {
        	if(i > 0){
        		dp[i][1] = distance[1][i];
        	}
            for (int j = 0; j <= k; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
           

        for (int i = 1; i <= len; i++) {
            for (int j = 2; j <= k && j <= i; j++) {
                for (int u = j; u <= i; u++) {
                    dp[i][j] = Math.min(dp[i][j], dp[u - 1][j - 1] + distance[u][i]);
                }
            }
        }
        return dp[len][k];
    }
}
